/*
题目：最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

    如果 x == y，那么两块石头都会被完全粉碎；
    如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
https://leetcode.cn/problems/last-stone-weight/
 */
public class LastStoneWeight {
    int last = 0;//表示最后一个元素

    public int lastStoneWeight(int[] stones) {
        //先构造大根堆，然后每次粉碎最大的两个石头
        last = stones.length;
        createBigHeap(stones);
        while (last > 1) {
            int one = stones[0];
            stones[0] = stones[--last];
            shiftDown(stones, 0);

            // stones[0] = Math.abs(one - stones[0]);
            // shiftDown(stones, 0);以下6行也能改成这样
            int two = stones[0];
            stones[0] = stones[--last];
            shiftDown(stones, 0);

            stones[last++] = one - two;
            shiftUp(stones, last - 1);
        }
        return stones[0];
    }

    private void createBigHeap(int[] heap) {
        //从最后一个双亲结点开始，建造大根堆
        for (int i = (last - 2) / 2; i >= 0; i--) {
            shiftDown(heap, i);
        }
    }

    //向下调整
    private void shiftDown(int[] heap, int parent) {
        int child = parent * 2 + 1;
        while (child < last) {
            if (child + 1 < last && heap[child] < heap[child + 1]) {
                child++;//保证child指向较大孩子结点
            }
            if (heap[parent] < heap[child]) {
                int tmp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    //向上调整
    private void shiftUp(int[] heap, int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (heap[child] > heap[parent]) {
                int tmp = heap[child];
                heap[child] = heap[parent];
                heap[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
}
